package com.salim.leetcode.$77;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 组合
 */
public class Combinations {

    public List<List<Integer>> combine(int n, int k) {
        return loop(new LinkedList<>(),1,n,k);
    }

    List<List<Integer>> loop(List<Integer> array,int start,int length,int k){
        List<List<Integer>> result = new ArrayList<>();
        if(k==0){
            result.add(array);
            return result;
        }
        for(int i=start;i<length-k+2;i++){
            List<Integer> newR = new LinkedList<>(array);
            newR.add(i);
            result.addAll(loop(newR,i+1,length,k-1));
        }
        return result;
    }
}
